﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;

namespace Lib
{
    public class FPAlgo
    {


        public TransactionData Data;
        public TransactionData FilterDatas;
        public Dictionary<List<TransactionValue>, int> fiList = new Dictionary<List<TransactionValue>, int>();
        public List<FrequentItem> FI = new List<FrequentItem>();


        public double minsup;
        public double mincof;
        public Dictionary<string, double> FrequentItemset;
        public long startTime;
        public long endTime;

        public FPAlgo(double supp, TransactionData data)
        {
            minsup = supp;
            Data = data;
        }

        public Dictionary<List<TransactionValue>, int> GetL1(TransactionData data)
        {

            var L1 = new Dictionary<List<TransactionValue>, int>();
            List<TransactionValue> items = GetItem(data);

            foreach (var item in items.FindAll(x => x.Count >= minsup).OrderByDescending(x => x.Count))
            {
                List<TransactionValue> key = new List<TransactionValue>();
                key.Add(new TransactionValue(item.Name, item.AttIndex, item.AttName));
                L1.Add(key, item.Count);
            }
            return L1;
        }

        public List<TransactionValue> GetItem(TransactionData data)
        {
            List<TransactionValue> uniqueItems = new List<TransactionValue>();
            foreach (var attvalue in data.Attributes)
            {
                TransactionValue v = new TransactionValue();
                foreach (var value in data.Transactions)
                {
                    v = value.Value.Find(x => x.AttIndex == attvalue.Index && x.AttName == attvalue.AttributeName);
                    if (v != null)
                    {
                        TransactionValue mem = uniqueItems.Find(y => y.AttIndex == v.AttIndex && y.Name == v.Name);
                        if (mem != null)
                            mem.Count++;
                        else
                            uniqueItems.Add(new TransactionValue(v));
                    }

                }
            }
            return uniqueItems;
        }
        /// <summary>
        /// Lọc dữ liệu theo tập L1.
        /// </summary>
        /// <param name="data"></param>
        /// <param name="L1"></param>
        /// <returns></returns>
        public TransactionData FilterData(TransactionData data, Dictionary<List<TransactionValue>, int> L1)
        {
            List<TransactionValue> source = new List<TransactionValue>();
            FilterDatas = new TransactionData();

            foreach (var s in L1.Keys)
            {
                source.AddRange(from v in s select v);
            }

            foreach (var tranValue in source)
            {
                FilterDatas.Attributes.Add(new DataAttribute(string.Format("{0}", tranValue.Name), null, tranValue.AttIndex));
            }

            foreach (var tran in data.Transactions)
            {
                List<TransactionValue> tranNew = new List<TransactionValue>();
                List<TransactionValue> tvalue = tran.Value;

                foreach (var att in FilterDatas.Attributes)
                {
                    var val = tvalue.Find(x => x.AttIndex == att.Index && x.Name == att.AttributeName);
                    if (val != null)
                        tranNew.Add(val);
                }
                FilterDatas.Transactions.Add(new Transaction(tran.Key, tranNew));
            }
            return FilterDatas;
        }

        public int countTree = 1;

        /// <summary>
        /// Tạo cây FPtree
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public FPTree createFptree(TransactionData data)
        {

            FPTree root = new FPTree();

            Dictionary<List<TransactionValue>, int> L1 = new Dictionary<List<TransactionValue>, int>();
            L1 = GetL1(data);
            if (L1.Count != 0)
            {
                root.createTable(L1);
                TransactionData newData = FilterData(data, L1);
                foreach (var tran in newData.Transactions)
                {
                    List<TransactionValue> val = tran.Value;
                    Insert_tree(val, root.root);
                }
                getHeader(root.HeaderTable, root.root, ref root.numPath);
            }
            countTree++;
            return root;
        }
        /// <summary>
        /// Tạo Header Table
        /// </summary>
        /// <param name="header"></param>
        /// <param name="root"></param>
        /// <param name="numPath"></param>
        public void getHeader(List<HeaderItem> header, FPNode root, ref int numPath)
        {
            foreach (var child in root.childs)
            {
                header.Find(x => x.ItemName == string.Format("{0}: {1}", child.AttName, child.Name)).NodeLink.Add(new FPNode { Name = child.Name, count = child.count, Parent = child.Parent, AttName = child.AttName, AttIndex = child.AttIndex });
                if (child.childs.Count == 0)
                    numPath++;
                getHeader(header, child, ref numPath);
            }
        }
        /// <summary>
        /// Tạo các nhánh của cay FPTree
        /// </summary>
        /// <param name="tran"></param>
        /// <param name="node"></param>
        public void Insert_tree(List<TransactionValue> tran, FPNode node)
        {
            FPNode child = node.getChilds(tran[0].Name);
            if (child != null)
            {
                child.count++;
            }
            else
            {
                child = new FPNode();
                child.count = 1;
                InfoFNode(tran, child);
                child.Parent = node;
                node.childs.Add(child);
            }
            tran.RemoveAt(0);
            if (tran.Count != 0)
            {
                Insert_tree(tran, child);
            }
        }

        private static void InfoFNode(List<TransactionValue> tran, FPNode child)
        {
            child.AttIndex = tran[0].AttIndex;
            child.AttName = tran[0].AttName;
            child.Name = tran[0].Name;
        }

        public bool recur = false; // biến xác định đệ quy khi đệ quy cây mới với temp.

        /// <summary>
        /// Thuật toán FP_Growth
        /// </summary>
        /// <param name="tree">Cây FP_tree</param>        
        public void FP_growth(FPTree tree)
        {
            if (tree != null)
            {
                List<HeaderItem> header = tree.HeaderTable;

                if (tree.numPath == 1)
                {
                    foreach (var item in tree.root.childs)
                    {
                        AddFI(tree, tree.Base, item);
                    }

                }
                else
                {
                    for (int i = header.Count - 1; i >= 0; i--)
                    {
                        List<TransactionValue> fiKey = new List<TransactionValue>();
                        FPNode newTemp = new FPNode { Name = header[i].AttValue, AttIndex = header[i].AttIndex, AttName = header[i].AttName, count = (int)header[i].SupportCount };
                        fiKey.Add(new TransactionValue(header[i].AttValue, header[i].AttIndex, header[i].AttName));
                        FrequentItem newFi = new FrequentItem();
                        List<FPNode> newbase = new List<FPNode>();
                        List<FPNode> oldbase = new List<FPNode>(tree.Base);

                        if (tree.Base.Count == 0)
                        {
                            newbase.Add(newTemp);
                        }
                        else
                        {
                            List<TransactionValue> itemTemp = GetFiKey(tree.Base);
                            itemTemp.ForEach(x => fiKey.Add(x));       // test                  
                            //fiKey.AddRange(itemTemp);
                            newbase = tree.Base;
                            newbase.Add(newTemp);
                        }
                        newFi.Name = fiKey.OrderBy(x => x.AttIndex).ToList();
                        newFi.Supp = (int)header[i].SupportCount;

                        FI.Add(newFi);

                        TransactionData newdata = new TransactionData();
                        CreateBaseCondition(header, header[i].ItemName, ref newdata);
                        FPTree newTree = new FPTree();
                        newTree = createFptree(newdata);
                        if (newTree.root.childs.Count != 0)
                        {

                            newTree.Base = newbase;
                            FP_growth(newTree);
                            tree.Base = oldbase;
                        }
                        else
                        {
                            tree.Base = new List<FPNode>();
                        }
                    }
                }
            }
        }

        private bool haveFI(List<TransactionValue> list, List<FrequentItem> FI)
        {

            List<FrequentItem> source = FI.FindAll(x => x.Name.Count == list.Count && list.Count == 1).ToList();
            foreach (var fi in source)
            {

                foreach (var item in list)
                {
                    if (fi.Name.Find(x => x.Name == item.Name && x.AttName == item.AttName) != null)
                        return true;

                }
            }
            return false;


        }

        private void AddFI(FPTree tree, List<FPNode> temp, FPNode item)
        {
            int support = tree.root.childs.Min(x => x.count);
            List<TransactionValue> result = new List<TransactionValue>();
            List<TransactionValue> fiKey = new List<TransactionValue>();
            fiKey = GetFiKey(temp);
            foreach (var c in tree.root.childs)
            {
                GetAllNode(c, ref result);
            }
            List<List<TransactionValue>> subFi = new List<List<TransactionValue>>();
            subFi = GetSubFi(result);

            foreach (var sub in subFi)
            {
                List<TransactionValue> tam = new List<TransactionValue>(fiKey);
                sub.ForEach(x => tam.Add(x));
                //tam.AddRange(sub);
                FrequentItem newFi = new FrequentItem();
                newFi.Name = tam.OrderBy(x => x.AttIndex).ToList();
                newFi.Supp = support;
                FI.Add(newFi); // test
            }
        }

        /// <summary>
        /// Tạo các tập con của tập phổ biến.
        /// </summary>
        /// <param name="fi"></param>
        /// <returns></returns>
        private List<List<TransactionValue>> GetSubFi(List<TransactionValue> fi)
        {
            List<List<TransactionValue>> result = new List<List<TransactionValue>>();
            int subsetCount = (int)Math.Pow(2, fi.Count());
            for (int i = 0; i < subsetCount; i++)
            {
                List<TransactionValue> subset = new List<TransactionValue>();
                for (int bitIndex = 0; bitIndex < fi.Count; bitIndex++)
                {
                    if (GetBit(i, bitIndex) == 1)
                    {
                        subset.Add(fi[bitIndex]);
                    }
                }
                if (subset.Count != 0)
                    result.Add(subset);
            }
            return result;
        }

        private int GetBit(int value, int position)
        {
            int bit = value & (int)Math.Pow(2, position);
            return (bit > 0 ? 1 : 0);
        }

        private List<TransactionValue> GetFiKey(List<FPNode> temp)
        {
            return temp.Select(x => new TransactionValue(x.Name, x.AttIndex, x.AttName)).ToList();
        }

        private void GetAllNode(FPNode item, ref List<TransactionValue> result)
        {
            result.Add(new TransactionValue(item.Name, item.AttIndex, item.AttName));
            foreach (var t in item.childs)
            {
                GetAllNode(t, ref result);
            }
        }

        void GetAllNode(FPNode item, ref string result)
        {
            result += item.Name;
            foreach (var i in item.childs)
            {
                GetAllNode(i, ref result);
            }
        }

        private Dictionary<List<TransactionValue>, int> SubFi(List<TransactionValue> result, int supp)
        {
            Dictionary<List<TransactionValue>, int> subsets = new Dictionary<List<TransactionValue>, int>();
            foreach (var item in result)
            {
                subsets.Add(result, supp);
            }
            return subsets;
        }

        void CreateBaseCondition(List<HeaderItem> table, string fi, ref TransactionData data) // Tao database cho alpha
        {
            List<FPNode> nodes = table.Find(x => x.ItemName == fi).NodeLink;
            int j = 0;
            List<DataAttribute> atts = new List<DataAttribute>();
            for (int i = 0; i < nodes.Count; i++)
            {
                List<TransactionValue> newTran = new List<TransactionValue>();
                infoBase(nodes[i], ref atts, ref newTran);
                if (newTran.Count != 0)
                {
                    for (int n = 0; n < nodes[i].count; n++)
                    {
                        data.Transactions.Add(new Transaction(j++, newTran));
                    }
                }
            }
            data.Attributes = atts;
        }

        private void infoBase(FPNode fPNode, ref List<DataAttribute> atts, ref List<TransactionValue> newTran)
        {
            if (fPNode.Parent.Name == null)
                return;
            else
            {
                newTran.Add(new TransactionValue(fPNode.Parent.Name, fPNode.Parent.AttIndex, fPNode.Parent.AttName));
                if (atts.Find(x => x.AttributeName == fPNode.Parent.AttName && x.Index == fPNode.Parent.AttIndex) == null)
                {
                    atts.Add(new DataAttribute(fPNode.Parent.AttName, null, fPNode.Parent.AttIndex));
                }
                infoBase(fPNode.Parent, ref atts, ref newTran);
            }
        }



    }
}
